/**
 * 给你两个单词word1 和word2， 请返回将word1转换成word2 所使用的最少操作数 。
 *
 * 你可以对一个单词进行如下三种操作：
 *
 * 插入一个字符
 * 删除一个字符
 * 替换一个字符
 *
 * 链接：https://leetcode.cn/problems/edit-distance
 */
class MinDistance {
    /**
     * 编辑距离（Edit Distance）：
     *  是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。
     *
     *
     * 方法：动态规划
     *
     * 状态：
     *  子状态：word1的前1，2，3，...m个字符转换成word2的前1，2，3，...n个字符需要的编辑距离
     * /*
     *  F(i,j):word1的前i个字符变成word2的前j个字符的编辑距离
     *
     * 状态递推：
     *  F(i,j) = min { F(i-1,j）+1, F(i,j-1) +1, F(i-1,j-1) +(w1[i]==w2[j]?0:1) }
     *  上式表示从删除，增加和替换操作中选择一个最小操作数
     *  F(i-1,j): w1[1,...,i-1]于w2[1,...,j]的编辑距离，删除w1[i]的字符--->F(i,j)
     *  F(i,j-1): w1[1,...,i]于w2[1,...,j-1]的编辑距离，增加一个字符--->F(i,j)
     *  F(i-1,j-1): w1[1,...,i-1]于w2[1,...,j-1]的编辑距离，如果w1[i]与w2[j]相同，
     *  不做任何操作，编辑距离不变，如果w1[i]与w2[j]不同，替换w1[i]的字符为w2[j]--->F(i,j)
     *
     * 初始化：
     *  初始化一定要是确定的值，如果这里不加入空串，初始值无法确定
     *  F(i,0) = i :word与空串的编辑距离，删除操作
     *  F(0,i) = i :空串与word的编辑距离，增加操作
     *
     * 返回结果：F(m,n)
     * @param word1
     * @param word2
     * @return
     */
    public int minDistance(String word1, String word2) {
        // word与空串之间的编辑距离为word的长度
        if (word1.isEmpty() || word2.isEmpty())
            return Math.max(word1.length(), word2.length());
        int len1 = word1.length();
        int len2 = word2.length();
        int[][] minDis = new int[len1 + 1][len2 + 1];
        // F(i,j)初始化
        for (int i = 0; i <= len1; ++i) {
            minDis[i][0] = i;
        }
        for (int i = 0; i <= len2; ++i) {
            minDis[0][i] = i;
        }
        for (int i = 1; i <= len1; ++i) {
            for (int j = 1; j <= len2; ++j) {
                // F(i,j) = min { F(i-1,j）+1, F(i,j-1) +1, F(i-1,j-1) +(w1[i]==w2[j]?0:1) }

                minDis[i][j] = 1 + Math.min(minDis[i - 1][j]
                        , minDis[i][j - 1]);
                // 判断word1的第i个字符是否与word2的第j个字符相等
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    // 字符相等，F(i-1,j-1)编辑距离不变
                    minDis[i][j] = Math.min(minDis[i][j]
                            , minDis[i - 1][j - 1]);
                } else {
                    // 字符不相等，F(i-1,j-1)编辑距离 + 1
                    minDis[i][j] = Math.min(minDis[i][j]
                            , minDis[i - 1][j - 1] + 1);
                }
            }
        }
        return minDis[len1][len2];
    }
}